//https://leetcode.cn/problems/move-zeroes/solutions/?envType=study-plan-v2&envId=top-100-liked
//插入排序的变种，永远记住最左边零的位置；
//官方解法：插入排序的变种，永远记住最左边零的位置；

#include <iostream>
#include <vector>
#include <map>
#include<unordered_map>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero_index = -1;
        for(size_t i=0;i<nums.size();++i){
            if(nums[i]==0 &&zero_index==-1) {
                zero_index=i;
            }else if (nums[i]!=0 && zero_index!=-1){
                std::swap(nums[i], nums[zero_index++]);
            }
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int i=1;i<nums.size();++i){
            for(int j=i-1;j>=0;--j){
                if(nums[j+1]!=0&&nums[j]==0){
                    std::swap(nums[j+1],nums[j]);
                }else{
                    break;
                }
            }
        }
    }
};	